# intervals = [[1,3],[6,9]]
# newInterval = [2,5]
# intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
# newInterval = [4,8]
# intervals = []
# newInterval = [5,7]
# intervals = [[1,5]]
# newInterval = [2,3]
intervals = [[1,5]]
newInterval = [2,7]
def insert(intervals,newInterval):
    #先判断是否会有重叠的情况
    ans=[]
    insert_left=newInterval[0]
    insert_right=newInterval[1]
    for i in range(len(intervals)):
        cur_left=intervals[i][0]
        cur_right=intervals[i][1]
        if cur_left>newInterval[1] or cur_right<newInterval[0]:
            #没有重叠的情况
            ans.append([cur_left,cur_right])
        else:
            #存在重叠的情况
            insert_left=min(insert_left,cur_left)
            insert_right=max(insert_right,cur_right)
    print("待插入串",[insert_left,insert_right])
    # if len(ans)==0:
    #     #是空串
    #     ans.append([insert_left,insert_right])
    # for i in range(len(ans)):
    #     if i==0 and insert_right<ans[i][0]:
    #         ans.insert(i,[insert_left,insert_right])
    #         break
    #     elif i>=0 and i<len(ans)-1:
    #         #不是第一个元素也不是最后一个
    #         if ans[i][1]<insert_left and ans[i+1][0]>insert_right:
    #             ans.insert(i+1,[insert_left,insert_right])
    #             break
    #     elif i==len(ans)-1 and ans[i][1]<insert_left:
    #         ans.append([insert_left,insert_right])
    ans.append([insert_left,insert_right])
    ans.sort(key=lambda x:x[0])
    return ans

print(insert(intervals,newInterval))

